{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 注意(attention)！开始做前必读项！\n",
    "\n",
    "- 所有的代码一定要在这个文件里面编写，不要自己创建一个新的文件\n",
    "- 对于提供的数据集，不要改存储地方，也不要修改文件名和内容\n",
    "- 确保到时候git pull之后我们可以直接运行这个 starter_code文件\n",
    "- 不要重新定义函数（如果我们已经定义好的），按照里面的思路来编写。当然，除了我们定义的部分，如有需要可以自行定义函数或者模块\n",
    "- 写完之后，重新看一下哪一部分比较慢，然后试图去优化。一个好的习惯是每写一部分就思考这部分代码的时间复杂度和空间复杂度，AI工程是的日常习惯！\n",
    "- 第一次作业很重要，一定要完成！ 相信会有很多的收获！"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 1: 搭建一个分词工具\n",
    "\n",
    "### Part 1.1  基于枚举方法来搭建中文分词工具\n",
    "\n",
    "此项目需要的数据：\n",
    "1. 综合类中文词库.xlsx： 包含了中文词，当做词典来用\n",
    "2. 以变量的方式提供了部分unigram概率 word_prob\n",
    "\n",
    "\n",
    "举个例子： 给定词典=[我们 学习 人工 智能 人工智能 未来 是]， 另外我们给定unigram概率：p(我们)=0.25, p(学习)=0.15, p(人工)=0.05, p(智能)=0.1, p(人工智能)=0.2, p(未来)=0.1, p(是)=0.15\n",
    "\n",
    "#### Step 1: 对于给定字符串：”我们学习人工智能，人工智能是未来“, 找出所有可能的分割方式\n",
    "- [我们，学习，人工智能，人工智能，是，未来]\n",
    "- [我们，学习，人工，智能，人工智能，是，未来]\n",
    "- [我们，学习，人工，智能，人工，智能，是，未来]\n",
    "- [我们，学习，人工智能，人工，智能，是，未来]\n",
    ".......\n",
    "\n",
    "\n",
    "#### Step 2: 我们也可以计算出每一个切分之后句子的概率\n",
    "- p(我们，学习，人工智能，人工智能，是，未来)= -log p(我们)-log p(学习)-log p(人工智能)-log p(人工智能)-log p(是)-log p(未来)\n",
    "- p(我们，学习，人工，智能，人工智能，是，未来)=-log p(我们)-log p(学习)-log p(人工)-log p(智能)-log p(人工智能)-log p(是)-log p(未来)\n",
    "- p(我们，学习，人工，智能，人工，智能，是，未来)=-log p(我们)-log p(学习)-log p(人工)-log p(智能)-log p(人工)-log p(智能)-log p(是)-log p(未来)\n",
    "- p(我们，学习，人工智能，人工，智能，是，未来)=-log p(我们)-log p(学习)-log p(人工智能)-log p(人工)-log p(智能)-log(是)-log p(未来)\n",
    ".....\n",
    "\n",
    "#### Step 3: 返回第二步中概率最大的结果"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": "酢\n做做事\n做做饭\n做做\n做作\n做主\n做针线\n做张做智\n做张做致\n做张做势\n1.0000000000000002\n"
    }
   ],
   "source": [
    "# TODO: 第一步： 从dic.txt中读取所有中文词。\n",
    "#  hint: 思考一下用什么数据结构来存储这个词典会比较好？ 要考虑我们每次查询一个单词的效率。 \n",
    "import xlrd\n",
    "workbook = xlrd.open_workbook(\".\\data\\综合类中文词库.xlsx\")\n",
    "worksheet = workbook.sheet_by_index(0)\n",
    "col_data = worksheet.col_values(0)\n",
    "col_index = [0.00001] * len(col_data)\n",
    "dic_words = dict(zip(col_data,col_index))   # 保存词典库中读取的单词\n",
    "\n",
    "i = 0\n",
    "for w in dic_words:\n",
    "    i += 1\n",
    "    print(w)\n",
    "    if i == 10:\n",
    "        break\n",
    "    \n",
    "\n",
    "# 以下是每一个单词出现的概率。为了问题的简化，我们只列出了一小部分单词的概率。 在这里没有出现的的单词但是出现在词典里的，统一把概率设置成为0.00001\n",
    "# 比如 p(\"学院\")=p(\"概率\")=...0.00001\n",
    "\n",
    "word_prob = {\"北京\":0.03,\"的\":0.08,\"天\":0.005,\"气\":0.005,\"天气\":0.06,\"真\":0.04,\"好\":0.05,\"真好\":0.04,\"啊\":0.01,\"真好啊\":0.02, \n",
    "             \"今\":0.01,\"今天\":0.07,\"课程\":0.06,\"内容\":0.06,\"有\":0.05,\"很\":0.03,\"很有\":0.04,\"意思\":0.06,\"有意思\":0.005,\"课\":0.01,\n",
    "             \"程\":0.005,\"经常\":0.08,\"意见\":0.08,\"意\":0.01,\"见\":0.005,\"有意见\":0.02,\"分歧\":0.04,\"分\":0.02, \"歧\":0.005}\n",
    "\n",
    "print (sum(word_prob.values()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "#  分数（10）\n",
    "## TODO 请编写word_segment_naive函数来实现对输入字符串的分词\n",
    "def word_segment_naive(input_str):\n",
    "    \"\"\"\n",
    "    1. 对于输入字符串做分词，并返回所有可行的分词之后的结果。\n",
    "    2. 针对于每一个返回结果，计算句子的概率\n",
    "    3. 返回概率最高的最作为最后结果\n",
    "    \n",
    "    input_str: 输入字符串   输入格式：“今天天气好”\n",
    "    best_segment: 最好的分词结果  输出格式：[\"今天\"，\"天气\"，\"好\"]\n",
    "    \"\"\"\n",
    "    segments = [] \n",
    "    # TODO： 第一步： 计算所有可能的分词结果，要保证每个分完的词存在于词典里，这个结果有可能会非常多。 \n",
    "    # 存储所有分词的结果。如果次字符串不可能被完全切分，则返回空列表(list)\n",
    "    # 格式为：segments = [[\"今天\"，“天气”，“好”],[\"今天\"，“天“，”气”，“好”],[\"今“，”天\"，“天气”，“好”],...]\n",
    "\n",
    "    if len(input_str) == 0:\n",
    "        return segments\n",
    "\n",
    "    for idx in range(1,len(input_str)+1):\n",
    "        word = input_str[0:idx]\n",
    "        if word in dic_words:\n",
    "            sub_string = word_segment_naive(input_str[idx:])\n",
    "           \n",
    "            if (len(sub_string) == 0) & (len(input_str[idx:]) == 0):\n",
    "                segments.append([word])\n",
    "            else:\n",
    "                for seg in sub_string:\n",
    "                    seg = [word] + seg\n",
    "                    segments.append(seg)\n",
    "    return segments\n",
    "    # TODO: 第二步：循环所有的分词结果，并计算出概率最高的分词结果，并返回\n",
    "    #best_segment = \n",
    "    #best_score = \n",
    "    #for seg in segments:\n",
    "        # TODO ...\n",
    "    \n",
    "    #return best_segment      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": "True\n"
    }
   ],
   "source": [
    "print(\"我\" in dic_words)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": "[['北', '京', '的', '天', '气', '真', '好', '啊'], ['北', '京', '的', '天', '气', '真好', '啊'], ['北', '京', '的', '天气', '真', '好', '啊'], ['北', '京', '的', '天气', '真好', '啊'], ['北京', '的', '天', '气', '真', '好', '啊'], ['北京', '的', '天', '气', '真好', '啊'], ['北京', '的', '天气', '真', '好', '啊'], ['北京', '的', '天气', '真好', '啊']]\n[['今', '天', '的', '课', '程', '内', '容', '很', '有', '意', '思'], ['今', '天', '的', '课', '程', '内', '容', '很', '有', '意思'], ['今', '天', '的', '课', '程', '内', '容', '很', '有意', '思'], ['今', '天', '的', '课', '程', '内', '容', '很', '有意思'], ['今', '天', '的', '课', '程', '内容', '很', '有', '意', '思'], ['今', '天', '的', '课', '程', '内容', '很', '有', '意思'], ['今', '天', '的', '课', '程', '内容', '很', '有意', '思'], ['今', '天', '的', '课', '程', '内容', '很', '有意思'], ['今', '天', '的', '课程', '内', '容', '很', '有', '意', '思'], ['今', '天', '的', '课程', '内', '容', '很', '有', '意思'], ['今', '天', '的', '课程', '内', '容', '很', '有意', '思'], ['今', '天', '的', '课程', '内', '容', '很', '有意思'], ['今', '天', '的', '课程', '内容', '很', '有', '意', '思'], ['今', '天', '的', '课程', '内容', '很', '有', '意思'], ['今', '天', '的', '课程', '内容', '很', '有意', '思'], ['今', '天', '的', '课程', '内容', '很', '有意思'], ['今天', '的', '课', '程', '内', '容', '很', '有', '意', '思'], ['今天', '的', '课', '程', '内', '容', '很', '有', '意思'], ['今天', '的', '课', '程', '内', '容', '很', '有意', '思'], ['今天', '的', '课', '程', '内', '容', '很', '有意思'], ['今天', '的', '课', '程', '内容', '很', '有', '意', '思'], ['今天', '的', '课', '程', '内容', '很', '有', '意思'], ['今天', '的', '课', '程', '内容', '很', '有意', '思'], ['今天', '的', '课', '程', '内容', '很', '有意思'], ['今天', '的', '课程', '内', '容', '很', '有', '意', '思'], ['今天', '的', '课程', '内', '容', '很', '有', '意思'], ['今天', '的', '课程', '内', '容', '很', '有意', '思'], ['今天', '的', '课程', '内', '容', '很', '有意思'], ['今天', '的', '课程', '内容', '很', '有', '意', '思'], ['今天', '的', '课程', '内容', '很', '有', '意思'], ['今天', '的', '课程', '内容', '很', '有意', '思'], ['今天', '的', '课程', '内容', '很', '有意思']]\n[['经', '常', '有', '意', '见', '分', '歧'], ['经', '常', '有', '意', '见', '分歧'], ['经', '常', '有', '意见', '分', '歧'], ['经', '常', '有', '意见', '分歧'], ['经', '常', '有意', '见', '分', '歧'], ['经', '常', '有意', '见', '分歧'], ['经', '常有', '意', '见', '分', '歧'], ['经', '常有', '意', '见', '分歧'], ['经', '常有', '意见', '分', '歧'], ['经', '常有', '意见', '分歧'], ['经常', '有', '意', '见', '分', '歧'], ['经常', '有', '意', '见', '分歧'], ['经常', '有', '意见', '分', '歧'], ['经常', '有', '意见', '分歧'], ['经常', '有意', '见', '分', '歧'], ['经常', '有意', '见', '分歧']]\n"
    }
   ],
   "source": [
    "# 测试\n",
    "print (word_segment_naive(\"北京的天气真好啊\"))\n",
    "print (word_segment_naive(\"今天的课程内容很有意思\"))\n",
    "print (word_segment_naive(\"经常有意见分歧\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 1.2  基于维特比算法来优化上述流程\n",
    "\n",
    "此项目需要的数据：\n",
    "1. 综合类中文词库.xlsx： 包含了中文词，当做词典来用\n",
    "2. 以变量的方式提供了部分unigram概率word_prob\n",
    "\n",
    "\n",
    "举个例子： 给定词典=[我们 学习 人工 智能 人工智能 未来 是]， 另外我们给定unigram概率：p(我们)=0.25, p(学习)=0.15, p(人工)=0.05, p(智能)=0.1, p(人工智能)=0.2, p(未来)=0.1, p(是)=0.15\n",
    "\n",
    "#### Step 1: 根据词典，输入的句子和 word_prob来创建带权重的有向图（Directed Graph） 参考：课程内容\n",
    "有向图的每一条边是一个单词的概率（只要存在于词典里的都可以作为一个合法的单词），这些概率已经给出（存放在word_prob）。\n",
    "注意：思考用什么方式来存储这种有向图比较合适？ 不一定只有一种方式来存储这种结构。 \n",
    "\n",
    "#### Step 2: 编写维特比算法（viterebi）算法来找出其中最好的PATH， 也就是最好的句子切分\n",
    "具体算法参考课程中讲过的内容\n",
    "\n",
    "#### Step 3: 返回结果\n",
    "跟PART 1.1的要求一致"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 分数（10）\n",
    "\n",
    "## TODO 请编写word_segment_viterbi函数来实现对输入字符串的分词\n",
    "def word_segment_viterbi(input_str):\n",
    "    \"\"\"\n",
    "    1. 基于输入字符串，词典，以及给定的unigram概率来创建DAG(有向图）。\n",
    "    2. 编写维特比算法来寻找最优的PATH\n",
    "    3. 返回分词结果\n",
    "    \n",
    "    input_str: 输入字符串   输入格式：“今天天气好”\n",
    "    best_segment: 最好的分词结果  输出格式：[\"今天\"，\"天气\"，\"好\"]\n",
    "    \"\"\"\n",
    "    \n",
    "    # TODO: 第一步：根据词典，输入的句子，以及给定的unigram概率来创建带权重的有向图（Directed Graph） 参考：课程内容\n",
    "    #      有向图的每一条边是一个单词的概率（只要存在于词典里的都可以作为一个合法的单词），这些概率在 word_prob，如果不在word_prob里的单词但在\n",
    "    #      词典里存在的，统一用概率值0.00001。\n",
    "    #      注意：思考用什么方式来存储这种有向图比较合适？ 不一定有只有一种方式来存储这种结构。 \n",
    "    graph = \n",
    "    \n",
    "    # TODO： 第二步： 利用维特比算法来找出最好的PATH， 这个PATH是P(sentence)最大或者 -log P(sentence)最小的PATH。\n",
    "    #              hint: 思考为什么不用相乘: p(w1)p(w2)...而是使用negative log sum:  -log(w1)-log(w2)-...\n",
    "    \n",
    "    \n",
    "    # TODO: 第三步： 根据最好的PATH, 返回最好的切分\n",
    "\n",
    "    return best_segment      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 测试\n",
    "print (word_segment_naive(\"北京的天气真好啊\"))\n",
    "print (word_segment_naive(\"今天的课程内容很有意思\")\n",
    "print (word_segment_naive(\"经常有意见分歧\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 分数（3）\n",
    "# TODO: 第一种方法和第二种方法的时间复杂度和空间复杂度分别是多少？\n",
    "第一个方法： \n",
    "时间复杂度= , 空间复杂度=\n",
    "\n",
    "第二个方法：\n",
    "时间复杂度= , 空间复杂度="
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 分数（2）\n",
    "# TODO：如果把上述的分词工具持续优化，有哪些可以考虑的方法？ （至少列出3点）\n",
    "- 0. （例）， 目前的概率是不完整的，可以考虑大量的语料库，然后从中计算出每一个词出现的概率，这样更加真实\n",
    "- 1.\n",
    "- 2.\n",
    "- 3. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Part 2:  搭建一个简单的问答系统"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "本次项目的目标是搭建一个基于检索式的简单的问答系统。至于什么是检索式的问答系统请参考课程直播内容/PPT介绍。 \n",
    "\n",
    "通过此项目，你将会有机会掌握以下几个知识点：\n",
    "1. 字符串操作   2. 文本预处理技术（词过滤，标准化）   3. 文本的表示（tf-idf, word2vec)  4. 文本相似度计算  5. 文本高效检索\n",
    "\n",
    "此项目需要的数据：\n",
    "1. dev-v2.0.json: 这个数据包含了问题和答案的pair， 但是以JSON格式存在，需要编写parser来提取出里面的问题和答案。 \n",
    "2. glove.6B: 这个文件需要从网上下载，下载地址为：https://nlp.stanford.edu/projects/glove/， 请使用d=100的词向量\n",
    "\n",
    "##### 检索式的问答系统\n",
    "问答系统所需要的数据已经提供，对于每一个问题都可以找得到相应的答案，所以可以理解为每一个样本数据是 <问题、答案>。 那系统的核心是当用户输入一个问题的时候，首先要找到跟这个问题最相近的已经存储在库里的问题，然后直接返回相应的答案即可。 举一个简单的例子：\n",
    "\n",
    "假设我们的库里面已有存在以下几个<问题,答案>：\n",
    "<\"贪心学院主要做什么方面的业务？”， “他们主要做人工智能方面的教育”>\n",
    "<“国内有哪些做人工智能教育的公司？”， “贪心学院”>\n",
    "<\"人工智能和机器学习的关系什么？\", \"其实机器学习是人工智能的一个范畴，很多人工智能的应用要基于机器学习的技术\">\n",
    "<\"人工智能最核心的语言是什么？\"， ”Python“>\n",
    ".....\n",
    "\n",
    "假设一个用户往系统中输入了问题 “贪心学院是做什么的？”， 那这时候系统先去匹配最相近的“已经存在库里的”问题。 那在这里很显然是 “贪心学院是做什么的”和“贪心学院主要做什么方面的业务？”是最相近的。 所以当我们定位到这个问题之后，直接返回它的答案 “他们主要做人工智能方面的教育”就可以了。 所以这里的核心问题可以归结为计算两个问句（query）之间的相似度。\n",
    "\n",
    "在本次项目中，你会频繁地使用到sklearn这个机器学习库。具体安装请见：http://scikit-learn.org/stable/install.html  sklearn包含了各类机器学习算法和数据处理工具，包括本项目需要使用的词袋模型，均可以在sklearn工具包中找得到。 另外，本项目还需要用到分词工具jieba, 具体使用方法请见 https://github.com/fxsjy/jieba"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2.1  第一部分： 读取文件，并把内容分别写到两个list里（一个list对应问题集，另一个list对应答案集）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 分数（5）\n",
    "def read_corpus():\n",
    "    \"\"\"\n",
    "    读取给定的语料库，并把问题列表和答案列表分别写入到 qlist, alist 里面。 在此过程中，不用对字符换做任何的处理（这部分需要在 Part 2.3里处理）\n",
    "    qlist = [\"问题1\"， “问题2”， “问题3” ....]\n",
    "    alist = [\"答案1\", \"答案2\", \"答案3\" ....]\n",
    "    务必要让每一个问题和答案对应起来（下标位置一致）\n",
    "    \"\"\"\n",
    "    assert len(qlist) == len(alist)  # 确保长度一样\n",
    "    return qlist, alist"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Part 2.2 理解数据（可视化分析/统计信息）\n",
    "对数据的理解是任何AI工作的第一步，需要充分对手上的数据有个更直观的理解。 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 分数（10）\n",
    "# TODO: 统计一下在qlist 总共出现了多少个单词？ 总共出现了多少个不同的单词？\n",
    "#       这里需要做简单的分词，对于英文我们根据空格来分词即可，其他过滤暂不考虑（只需分词）\n",
    "\n",
    "print (word_total)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# TODO: 统计一下qlist中每个单词出现的频率，并把这些频率排一下序，然后画成plot. 比如总共出现了总共7个不同单词，而且每个单词出现的频率为 4, 5,10,2, 1, 1,1\n",
    "#       把频率排序之后就可以得到(从大到小) 10, 5, 4, 2, 1, 1, 1. 然后把这7个数plot即可（从大到小）\n",
    "#       需要使用matplotlib里的plot函数。y轴是词频"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# TODO： 从上面的图中能观察到什么样的现象？ 这样的一个图的形状跟一个非常著名的函数形状很类似，能所出此定理吗？ \n",
    "#       hint: [XXX]'s law\n",
    "# \n",
    "# "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# TODO: 在qlist和alist里出现次数最多的TOP 10单词分别是什么？ \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.3 文本预处理\n",
    "次部分需要尝试做文本的处理。在这里我们面对的是英文文本，所以任何对英文适合的技术都可以考虑进来。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 分数（10）\n",
    "\n",
    "# TODO: 对于qlist, alist做文本预处理操作。 可以考虑以下几种操作：\n",
    "#       1. 停用词过滤 （去网上搜一下 \"english stop words list\"，会出现很多包含停用词库的网页，或者直接使用NLTK自带的）   \n",
    "#       2. 转换成lower_case： 这是一个基本的操作   \n",
    "#       3. 去掉一些无用的符号： 比如连续的感叹号！！！， 或者一些奇怪的单词。\n",
    "#       4. 去掉出现频率很低的词：比如出现次数少于10,20....\n",
    "#       5. 对于数字的处理： 分词完只有有些单词可能就是数字比如44，415，把所有这些数字都看成是一个单词，这个新的单词我们可以定义为 \"#number\"\n",
    "#       6. stemming（利用porter stemming): 因为是英文，所以stemming也是可以做的工作\n",
    "#       7. 其他（如果有的话）\n",
    "#       请注意，不一定要按照上面的顺序来处理，具体处理的顺序思考一下，然后选择一个合理的顺序\n",
    "#  hint: 停用词用什么数据结构来存储？ 不一样的数据结构会带来完全不一样的效率！ \n",
    "\n",
    "qlist, alist =    # 更新后的"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# TODO: 在前面步骤里，我们删除了出现次数比较少的单词，那你选择的阈值是多少（小于多少的去掉？）， 这个阈值是根据什么来选择的？ \n",
    "# "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.4 文本表示\n",
    "当我们做完关键的预处理过程之后，就需要把每一个文本转换成向量。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 分数（10）\n",
    "\n",
    "# TODO: 把qlist中的每一个问题字符串转换成tf-idf向量, 转换之后的结果存储在X矩阵里。 X的大小是： N* D的矩阵。 这里N是问题的个数（样本个数），\n",
    "#       D是字典库的大小。 \n",
    "\n",
    "vectorizer =  # 定义一个tf-idf的vectorizer\n",
    "\n",
    "X =   # 结果存放在X矩阵"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# TODO: 矩阵X有什么特点？ 计算一下它的稀疏度\n",
    "\n",
    "print (sparsity)  # 打印出稀疏度(sparsity)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.5 对于用户的输入问题，找到相似度最高的TOP5问题，并把5个潜在的答案做返回"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 分数（10）\n",
    "\n",
    "def top5results(input_q):\n",
    "    \"\"\"\n",
    "    给定用户输入的问题 input_q, 返回最有可能的TOP 5问题。这里面需要做到以下几点：\n",
    "    1. 对于用户的输入 input_q 首先做一系列的预处理，然后再转换成tf-idf向量（利用上面的vectorizer)\n",
    "    2. 计算跟每个库里的问题之间的相似度\n",
    "    3. 找出相似度最高的top5问题的答案\n",
    "    \"\"\"\n",
    "    \n",
    "    top_idxs = []  # top_idxs存放相似度最高的（存在qlist里的）问题的下表 \n",
    "                   # hint: 利用priority queue来找出top results. 思考为什么可以这么做？ \n",
    "    \n",
    "    return alist[top_idxs]  # 返回相似度最高的问题对应的答案，作为TOP5答案    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# TODO: 编写几个测试用例，并输出结果\n",
    "print (top5results(\"\"))\n",
    "print (top5results(\"\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 分数（5）\n",
    "\n",
    "# TODO: 上面的top5results算法的时间复杂度和空间复杂度分别是多少？\n",
    "\n",
    "时间复杂度 = O()， 空间复杂度 = O()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.6 利用倒排表的优化。 \n",
    "上面的算法，一个最大的缺点是每一个用户问题都需要跟库里的所有的问题都计算相似度。假设我们库里的问题非常多，这将是效率非常低的方法。 这里面一个方案是通过倒排表的方式，先从库里面找到跟当前的输入类似的问题描述。然后针对于这些candidates问题再做余弦相似度的计算。这样会节省大量的时间。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 分数（10）\n",
    "\n",
    "# TODO: 基于倒排表的优化。在这里，我们可以定义一个类似于hash_map, 比如 inverted_index = {}， 然后存放包含每一个关键词的文档出现在了什么位置，\n",
    "#       也就是，通过关键词的搜索首先来判断包含这些关键词的文档（比如出现至少一个），然后对于candidates问题做相似度比较。\n",
    "# \n",
    "inverted_idx = {}  # 定一个一个简单的倒排表\n",
    "def top5results_invidx(input_q):\n",
    "    \"\"\"\n",
    "    给定用户输入的问题 input_q, 返回最有可能的TOP 5问题。这里面需要做到以下几点：\n",
    "    1. 利用倒排表来筛选 candidate\n",
    "    2. 对于用户的输入 input_q 首先做一系列的预处理，然后再转换成tf-idf向量（利用上面的vectorizer)\n",
    "    3. 计算跟每个库里的问题之间的相似度\n",
    "    4. 找出相似度最高的top5问题的答案\n",
    "    \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# TODO: 编写几个测试用例，并输出结果\n",
    "print (top5results_invidx(\"\"))\n",
    "print (top5results_invidx(\"\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 分数（3）\n",
    "\n",
    "# TODO: 上面的top5results算法的时间复杂度和空间复杂度分别是多少？\n",
    "\n",
    "时间复杂度 = O()， 空间复杂度 = O()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.7 基于词向量的文本表示\n",
    "上面所用到的方法论是基于词袋模型（bag-of-words model）。这样的方法论有两个主要的问题：1. 无法计算词语之间的相似度  2. 稀疏度很高。 在2.7里面我们\n",
    "讲采用词向量作为文本的表示。词向量方面需要下载： https://nlp.stanford.edu/projects/glove/ （请下载glove.6B.zip），并使用d=100的词向量（100维）。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 分数（10）\n",
    "\n",
    "# TODO\n",
    "emb = # 读取每一个单词的嵌入。这个是 D*H的矩阵，这里的D是词典库的大小， H是词向量的大小。 这里面我们给定的每个单词的词向量，那句子向量怎么表达？\n",
    "      # 其中，最简单的方式 句子向量 = 词向量的平均（出现在问句里的）， 如果给定的词没有出现在词典库里，则忽略掉这个词。\n",
    "\n",
    "def top5results_emb(input_q):\n",
    "    \"\"\"\n",
    "    给定用户输入的问题 input_q, 返回最有可能的TOP 5问题。这里面需要做到以下几点：\n",
    "    1. 利用倒排表来筛选 candidate\n",
    "    2. 对于用户的输入 input_q，转换成句子向量\n",
    "    3. 计算跟每个库里的问题之间的相似度\n",
    "    4. 找出相似度最高的top5问题的答案\n",
    "    \"\"\"\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# TODO: 编写几个测试用例，并输出结果\n",
    "print (top5results_emb(\"\"))\n",
    "print (top5results_emb(\"\"))\n",
    "\n",
    "# 我们在验收作业时在后台会建立几个测试用例，来验证返回的准确性。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### 2.8 做完本次项目做完之后有什么收获？ \n",
    "\n",
    "#分数（2）\n",
    "\n",
    "回答 = “”"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.0-final"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}